package Review.MapAndSet;

// key-value 模型
public class HashBuck {
   static class Node {
      public int key;
      public int val;
      public Node next;

      public Node(int key, int val) {
         this.key = key;
         this.val = val;
      }
   }

   public Node[] array = new Node[10];
   public int usedSize;
   public static final double LOAD_FACTOR = 0.75f;

   public void put(int key, int val) {
      int index = key % array.length;
      Node cur = array[index];
      Node node = new Node(key, val);
      while (cur != null) {
         if (cur.key == key) {
            cur.val = val;
         }
         cur = cur.next;
      }
      //走到这里说明没有找到当前链表中有key这个节点
      node.next = array[index];
      array[index] = node;
      usedSize++;
      //走到这里说明数组容量不够要扩容
      if (loadfactor()>=LOAD_FACTOR){
         resize();
      }
   }

   private void resize() {
      Node[] num = new Node[2*array.length];
      for (int i=0;i<array.length;i++){
         Node cur = array[i];
         while (cur !=null){
            int index = cur.key%num.length;
            Node prev = cur.next;
            cur.next = num[index];
            num[index] = cur;
            cur = prev;
         }
      }
   }
   private double loadfactor(){
      return  usedSize*1.0/array.length;
   }
   public int getVal(int key){
      int index = key%array.length;
      Node cur = array[index];
      while (cur !=null){
         if (cur.key==key){
            return cur.val;
         }
         cur = cur.next;
      }
      return 0;
   }
}
